"""
使用动态规划，解决问题53

维护一个数组，记录两个值：
1. 从0到该元素为止，最右侧为该元素的最大和。left_max[n]=max(left_max[n-1],0)+nums[n]
2. 同样是这一段元素，整体的最大和。max[n]=max(max[n-1],left_max[n])

维护到末尾，则可得到所有元素的最大连续和。
思想虽然是动态规划，但由于只用到了上一个索引的元素，因此只维护常量元素即可。

"""

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        
        global_max=left_max=nums[0]
        for i in range(1,len(nums)):
            left_max=max(left_max,0)+nums[i]
            global_max=max(global_max,left_max)

        return global_max

if __name__=='__main__':
    nums=[5,4,-1,7,8]

    s = Solution()
    res=s.maxSubArray(nums)
    print(res)


    pass